//
// Created by shenbin on 2022/5/10.
// https://leetcode.cn/problems/binary-tree-inorder-traversal/
//

#ifndef ALGORITHM_TRAINNING_C05_LC94_H
#define ALGORITHM_TRAINNING_C05_LC94_H

#include <vector>

using namespace std;

/**
 * 中序遍历：左根右
 */
class LeetCode94 {
public:
    vector<int> inorderTraversal(TreeNode *root) {
        dfs(root);
        return seq;
    }

private:
    struct TreeNode {
        int val;
        TreeNode *left;
        TreeNode *right;

        TreeNode() : val(0), left(nullptr), right(nullptr) {}

        TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

        TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
    };

    vector<int> seq;

    void dfs(TreeNode* root){
        if (root == nullptr) return;
        dfs(root->left);
        seq.push_back(root->val);
        dfs(root->right);
    }
};

#endif //ALGORITHM_TRAINNING_C05_LC94_H
